1. Field of the Invention
This invention relates to a method for detecting collisions in a transmission channel using a distributed queueing random access protocol (DQRAP) wherein broadcast channel time is divided into a plurality of slots, each of which includes one data slot and one or more control minislots, and each of a plurality of sending stations maintains two common distributed queues. One queue, the data transmission queue, is used to organize the order of data transmission, and the other queue, the collision resolution queue, is used to resolve collisions that have occurred and to prevent collisions by new arrivals. The protocol includes data transmission rules, request transmission rules and queueing discipline rules.
2. Description of Prior Art
Investigation of multiple, random access control methods has been an active research area since as early as 1970. The well known CSMA protocols were then developed and later followed by multiple access methods which utilized various forms of feedback to improve performance by reducing or avoiding the occurrence of collisions. These included collision resolution schemes, now called tree-and-window collision resolution algorithms (CRA). The CSMA protocols achieved high throughput with minimal delay with low offered loads, and they have gained wide application in local area networks. In fact with zero propagation delay, collisions in slotted CSMA can be completely avoided and the performance of CSMA then corresponds to that of a perfect scheduling protocol, such as an M/D/1 queue. However, the CSMA protocols are not stable when traffic is heavy and while dynamic control mechanisms can improve performance, the unstable nature cannot be changed.
The first CRA included a tree algorithm which achieved a maximum throughput of 0.43, and was stable for all input rates of less than 0.43. This stable characteristic of the tree algorithm has attracted much attention in both the communications and information theory areas. The tree algorithm was improved by increasing the maximum throughput to 0.462. The next improvement was the 0.487 window protocol. The tree and window protocols are based on efficient use of channel feedback to resolve collisions and require transmitter coordination. It has been shown that the upper bound of throughput of all algorithms based on ternary feedback is 0.568, the tightest upper bound to date.
It is widely believed that the best achievable throughput is in the neighborhood of 0.5. If the amount of channel feedback is increased to indicate the number of packets involved in each collision, then throughput up to one may be achieved. However, the known algorithms in this context achieve only 0.533 throughput. Some known protocols achieve higher throughput than 0.5 by using control minislots (CMS) to obtain extra feedback. Among such known protocols, the announced arrival random access protocols (AARA) achieve the best performance with respect to throughput and delay characteristics. With three minislots the AARA protocol achieves a throughput of 0.853. However, to achieve throughput approaching one, the AARA protocol must use an infinite number of minislots. Obviously, the AARA protocols do not achieve or approach the bound of performance in this context. All existing tree protocols seem to use data slots to resolve collisions. In this process, channel capacity is lost either to empty slots or to collisions. All suggested improvements to tree protocols increased the channel throughput by reducing empty slots and collided slots, but none eliminated this type of loss.